package LeetCode.Hash;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * @author : LdLtd
 * @Date : 2023/7/23
 * @Description:128. 最长连续序列
 */
public class longest_consecutive_sequence {
    class Solution {
        public int longestConsecutive(int[] nums) {
            Set<Integer> set = new HashSet<>();
            for (int num : nums) {
                set.add(num);
            }
            int maxL = 0;
            for (Integer integer : set) {
                if (!set.contains(integer - 1)) {
                    int nu = integer;
                    int tem = 1;
                    while (set.contains(nu + 1)) {
                        nu += 1;
                        tem += 1;
                    }
                    maxL = Math.max(maxL, tem);
                }
            }
            return maxL;
        }

        /*
        * 用哈希表存储每个端点值对应连续区间的长度
            若数已在哈希表中：跳过不做处理
            若是新数加入：
            取出其左右相邻数已有的连续区间长度 left 和 right
            计算当前数的区间长度为：cur_length = left + right + 1
            根据 cur_length 更新最大长度 max_length 的值
            更新区间两端点的长度值
            *
=================================================================
            * 首先，定义一个哈希表（用于判断某个数是否存在哈希表中）
            *
            然后遍历数组
            如果当前数num存在哈希表，那么跳过
            如果当前数num不存在哈希表中，那么查找num-1和num+1这两个数是不是在哈希表中
            比如 num是5
            1234 678都在哈希表中
            遍历数组的时候，遇到1234678都会掠过
            此时哈希表中，1的位置和4存的值都是4（证明1或者4所在的连续长度是4）
            同理 6和8存的值都是3
            那么此时5进来之后，看看4和6在不在哈希表内，如果在的话，一定是端点，一定能获取到值
            所以5进来之后，发现左边有4个连续的，右边有3个连续的，加上自己一个，那么组成一个大连续的
            4+1+3 = 8
            所以要更新当前最长连续串的端点，也就是1的位置（5-4），8的位置（5+3），更新长度为8
            只需要端点存值就行，因为端点中的值在遍历的时候如果在哈希表中就会略过
            如果这个时候9又进来，那么它获取到8的位置有8，10的位置有0
            更新连续子串长度（8+1+0）
            所以更新左端点1（9-8）的值为9，右端点9（9+0）的值为9
*/
        public int longestConsecutive1(int[] nums) {
            Map<Integer, Integer> map = new HashMap<>();
            int maxL = 0;
            for (int num : nums) {
                if (!map.containsKey(num)) {
                    int l = map.getOrDefault(num - 1, 0);
                    int r = map.getOrDefault(num + 1, 0);
                    int tem = l + r + 1;
                    maxL = Math.max(maxL, tem);
                    map.put(num, tem);
                    map.put(num - l, tem);
                    map.put(num + r, tem);

                }
            }
            return maxL;
        }
    }
}